package com.evan.review.basic.collection;

import android.os.Bundle;
import android.widget.TextView;
import androidx.appcompat.app.AppCompatActivity;
import com.evan.review.R;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Deque;

/**
 * LinkedList详解Activity
 * 
 * 本Activity详细介绍LinkedList的实现原理、特性和使用方法：
 * 1. LinkedList的底层数据结构与实现
 * 2. LinkedList常用操作与时间复杂度
 * 3. LinkedList作为List、Queue、Deque的使用
 * 4. LinkedList与ArrayList的对比
 * 5. LinkedList常见面试题与最佳实践
 */
public class LinkedListActivity extends AppCompatActivity {
    
    private TextView tvOutput;
    
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_data_structure);
        
        setTitle("LinkedList详解");
        
        tvOutput = findViewById(R.id.tv_output);
        
        // 展示LinkedList基本原理
        demonstrateLinkedListPrinciple();
        
        // 展示LinkedList作为List使用
        demonstrateLinkedListAsList();
        
        // 展示LinkedList作为Queue/Deque使用
        demonstrateLinkedListAsQueue();
        
        // 展示LinkedList与ArrayList比较
        demonstrateComparisonWithArrayList();
        
        // 展示LinkedList常见面试题
        demonstrateInterviewQuestions();
    }
    
    /**
     * 展示LinkedList的基本原理
     */
    private void demonstrateLinkedListPrinciple() {
        StringBuilder output = new StringBuilder();
        output.append("=== LinkedList底层原理 ===\n\n");
        
        // 1. 基本数据结构
        output.append("1. 基本数据结构：\n");
        output.append("• 底层基于双向链表实现\n");
        output.append("• 核心内部类：\n");
        output.append("  private static class Node<E> {\n");
        output.append("      E item;            // 节点值\n");
        output.append("      Node<E> next;      // 后继节点\n");
        output.append("      Node<E> prev;      // 前驱节点\n");
        output.append("  }\n\n");
        
        output.append("• 核心字段：\n");
        output.append("  - Node<E> first: 链表的头结点\n");
        output.append("  - Node<E> last: 链表的尾结点\n");
        output.append("  - int size: 链表中的节点数量\n\n");
        
        // 2. 实现的接口
        output.append("2. 实现的接口：\n");
        output.append("• List<E>: 作为列表使用\n");
        output.append("• Deque<E>: 作为双端队列使用\n");
        output.append("• Cloneable: 支持克隆\n");
        output.append("• Serializable: 支持序列化\n\n");
        
        // 3. 核心特性
        output.append("3. 核心特性：\n");
        output.append("• 实现了List和Deque接口，可作为列表和双端队列使用\n");
        output.append("• 允许添加null元素\n");
        output.append("• 非线程安全\n");
        output.append("• 按插入顺序排列元素\n");
        output.append("• 遍历较慢，但插入删除较快\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示LinkedList作为List使用
     */
    private void demonstrateLinkedListAsList() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== LinkedList作为List使用 ===\n\n");
        
        // 创建LinkedList
        List<String> list = new LinkedList<>();
        list.add("Java");
        list.add("Kotlin");
        list.add("Swift");
        
        // 1. 添加元素
        output.append("1. 添加元素：\n");
        output.append("List<String> list = new LinkedList<>();\n");
        output.append("list.add(\"Java\");       // 末尾添加, O(1)\n");
        output.append("list.add(\"Kotlin\");     // 当前list: [Java, Kotlin]\n");
        output.append("list.add(1, \"Python\");  // 指定位置添加, O(n)\n");
        list.add(1, "Python"); 
        output.append("// 当前list: " + list + "\n\n");
        
        // 2. 获取元素
        output.append("2. 获取元素：\n");
        output.append("list.get(0);              // 返回 Java, O(n) - 但获取首尾元素是O(1)\n");
        output.append("((LinkedList<String>)list).getFirst();  // 返回 Java, O(1)\n");
        output.append("((LinkedList<String>)list).getLast();   // 返回 Swift, O(1)\n\n");
        
        // 3. 更新元素
        output.append("3. 更新元素：\n");
        output.append("list.set(1, \"C++\");     // 替换索引1处元素为C++, O(n)\n");
        list.set(1, "C++");
        output.append("// 当前list: " + list + "\n\n");
        
        // 4. 删除元素
        output.append("4. 删除元素：\n");
        output.append("list.remove(0);           // 删除索引0处元素, O(1)\n");
        list.remove(0);
        output.append("// 当前list: " + list + "\n");
        output.append("list.remove(\"C++\");     // 删除值为C++的元素, O(n)\n");
        list.remove("C++");
        output.append("// 当前list: " + list + "\n\n");
        
        // 5. 专有方法
        output.append("5. LinkedList专有方法：\n");
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("A");
        linkedList.add("B");
        
        output.append("LinkedList<String> linkedList = new LinkedList<>();\n");
        output.append("linkedList.add(\"A\");\n");
        output.append("linkedList.add(\"B\");    // 当前: [A, B]\n");
        output.append("linkedList.addFirst(\"X\"); // 添加到开头, O(1)\n");
        linkedList.addFirst("X");
        output.append("// 当前: " + linkedList + "\n");
        output.append("linkedList.addLast(\"Z\");  // 添加到末尾, O(1)\n");
        linkedList.addLast("Z");
        output.append("// 当前: " + linkedList + "\n");
        output.append("linkedList.removeFirst();   // 删除首元素, O(1), 返回 X\n");
        linkedList.removeFirst();
        output.append("// 当前: " + linkedList + "\n");
        output.append("linkedList.removeLast();    // 删除尾元素, O(1), 返回 Z\n");
        linkedList.removeLast();
        output.append("// 当前: " + linkedList + "\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示LinkedList作为Queue/Deque使用
     */
    private void demonstrateLinkedListAsQueue() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== LinkedList作为队列使用 ===\n\n");
        
        // 1. 作为Queue使用
        output.append("1. 作为Queue使用：\n");
        output.append("Queue<String> queue = new LinkedList<>();\n");
        
        Queue<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");
        
        output.append("queue.offer(\"First\");   // 添加元素到队尾\n");
        output.append("queue.offer(\"Second\");  // 添加元素到队尾\n");
        output.append("queue.offer(\"Third\");   // 添加元素到队尾\n");
        output.append("// 当前queue: " + queue + "\n");
        output.append("queue.peek();             // 查看队首元素，不删除: " + queue.peek() + "\n");
        output.append("queue.poll();             // 获取并删除队首元素: " + queue.poll() + "\n");
        output.append("// 当前queue: " + queue + "\n\n");
        
        // 2. 作为Deque使用
        output.append("2. 作为双端队列（Deque）使用：\n");
        output.append("Deque<String> deque = new LinkedList<>();\n");
        
        Deque<String> deque = new LinkedList<>();
        deque.addFirst("Front");
        deque.addLast("Back");
        
        output.append("deque.addFirst(\"Front\"); // 添加到队首\n");
        output.append("deque.addLast(\"Back\");   // 添加到队尾\n");
        output.append("// 当前deque: " + deque + "\n");
        output.append("deque.peekFirst();         // 查看队首元素: " + deque.peekFirst() + "\n");
        output.append("deque.peekLast();          // 查看队尾元素: " + deque.peekLast() + "\n");
        output.append("deque.pollFirst();         // 获取并删除队首元素: " + deque.pollFirst() + "\n");
        output.append("deque.pollLast();          // 获取并删除队尾元素: " + deque.pollLast() + "\n");
        output.append("// 当前deque: " + deque + "\n\n");
        
        // 3. 作为栈使用
        output.append("3. 作为栈使用：\n");
        output.append("Deque<String> stack = new LinkedList<>();\n");
        
        Deque<String> stack = new LinkedList<>();
        stack.push("Bottom");
        stack.push("Middle");
        stack.push("Top");
        
        output.append("stack.push(\"Bottom\");   // 压栈\n");
        output.append("stack.push(\"Middle\");   // 压栈\n");
        output.append("stack.push(\"Top\");      // 压栈\n");
        output.append("// 当前stack: " + stack + "\n");
        output.append("stack.peek();             // 查看栈顶元素: " + stack.peek() + "\n");
        output.append("stack.pop();              // 弹出栈顶元素: " + stack.pop() + "\n");
        output.append("stack.pop();              // 弹出栈顶元素: " + stack.pop() + "\n");
        output.append("// 当前stack: " + stack + "\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示LinkedList与ArrayList的比较
     */
    private void demonstrateComparisonWithArrayList() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== LinkedList与ArrayList比较 ===\n\n");
        
        // 1. 性能比较
        output.append("1. 性能比较：\n");
        output.append("┌───────────────────┬─────────────┬─────────────┐\n");
        output.append("│ 操作              │ ArrayList   │ LinkedList  │\n");
        output.append("├───────────────────┼─────────────┼─────────────┤\n");
        output.append("│ 随机访问 get(i)   │ O(1)        │ O(n)        │\n");
        output.append("│ 首尾访问          │ O(1)        │ O(1)        │\n");
        output.append("│ 中间位置添加/删除 │ O(n)        │ O(n)*       │\n");
        output.append("│ 首尾添加/删除     │ 尾部O(1)    │ O(1)        │\n");
        output.append("│                   │ 首部O(n)    │             │\n");
        output.append("│ 内存占用          │ 少          │ 较多        │\n");
        output.append("└───────────────────┴─────────────┴─────────────┘\n");
        output.append("* 虽然LinkedList插入操作是O(n)，但实际插入只需O(1)，O(n)主要用于定位\n\n");
        
        // 2. 适用场景
        output.append("2. 适用场景：\n");
        output.append("• ArrayList适合：\n");
        output.append("  - 频繁随机访问\n");
        output.append("  - 较少插入删除操作\n");
        output.append("  - 迭代遍历为主\n");
        output.append("  - 内存紧张\n\n");
        
        output.append("• LinkedList适合：\n");
        output.append("  - 频繁在两端添加/删除\n");
        output.append("  - 作为队列或栈使用\n");
        output.append("  - 不关心随机访问性能\n");
        output.append("  - 内存充足\n\n");
        
        // 3. 场景选择建议
        output.append("3. 选择建议：\n");
        output.append("• 默认首选ArrayList，除非有明确的LinkedList优势场景\n");
        output.append("• 需要频繁随机访问（通过索引）时，选择ArrayList\n");
        output.append("• 需要频繁在首部添加/删除元素时，选择LinkedList\n");
        output.append("• 需要队列/栈功能时，选择LinkedList\n");
        output.append("• 尽量避免在中间位置频繁插入删除，两者都不高效\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 展示LinkedList常见面试题
     */
    private void demonstrateInterviewQuestions() {
        StringBuilder output = new StringBuilder();
        output.append("\n=== LinkedList面试题 ===\n\n");
        
        // 1. LinkedList底层实现
        output.append("1. LinkedList底层实现原理是什么？\n");
        output.append("答：LinkedList基于双向链表实现：\n");
        output.append("• 每个节点包含三部分：前驱指针、元素值、后继指针\n");
        output.append("• 维护了first和last两个指针，分别指向链表的头和尾\n");
        output.append("• 对链表首尾的操作是O(1)复杂度\n");
        output.append("• 对链表中间的操作是O(n)复杂度（需要遍历定位）\n\n");
        
        // 2. ArrayList和LinkedList区别
        output.append("2. LinkedList与ArrayList的主要区别？\n");
        output.append("答：主要区别包括：\n");
        output.append("• 内部结构：ArrayList基于动态数组；LinkedList基于双向链表\n");
        output.append("• 随机访问：ArrayList支持高效随机访问O(1)；LinkedList需要遍历链表O(n)\n");
        output.append("• 插入删除：LinkedList在首尾插入删除更高效O(1)；ArrayList在末尾插入删除较高效，在首部或中间插入删除需要移动元素O(n)\n");
        output.append("• 内存消耗：LinkedList需要存储前后指针，每个元素占用更多内存\n");
        output.append("• 实现接口：LinkedList额外实现了Deque接口，可作为队列或栈使用\n\n");
        
        // 3. 如何选择ArrayList和LinkedList
        output.append("3. 如何选择ArrayList和LinkedList？\n");
        output.append("答：选择依据：\n");
        output.append("• 选择ArrayList的场景：\n");
        output.append("  - 需要频繁随机访问元素\n");
        output.append("  - 集合大小相对稳定，插入删除较少\n");
        output.append("  - 需要高效遍历\n");
        output.append("• 选择LinkedList的场景：\n");
        output.append("  - 需要频繁在首尾位置添加/删除元素\n");
        output.append("  - 需要实现队列、栈等数据结构\n");
        output.append("  - 不需要随机访问\n\n");
        
        // 4. LinkedList实现栈和队列
        output.append("4. LinkedList如何实现栈和队列？\n");
        output.append("答：LinkedList实现了Deque接口，可以直接用作栈和队列：\n");
        output.append("• 作为栈（LIFO）：\n");
        output.append("  Deque<E> stack = new LinkedList<>();\n");
        output.append("  stack.push(e);     // 入栈\n");
        output.append("  stack.pop();       // 出栈\n");
        output.append("  stack.peek();      // 查看栈顶\n\n");
        
        output.append("• 作为队列（FIFO）：\n");
        output.append("  Queue<E> queue = new LinkedList<>();\n");
        output.append("  queue.offer(e);    // 入队\n");
        output.append("  queue.poll();      // 出队\n");
        output.append("  queue.peek();      // 查看队首\n\n");
        
        // 5. LinkedList线程安全问题
        output.append("5. LinkedList是线程安全的吗？如何实现线程安全？\n");
        output.append("答：LinkedList非线程安全。线程安全解决方案：\n");
        output.append("• 使用Collections.synchronizedList包装：\n");
        output.append("  List<E> syncList = Collections.synchronizedList(new LinkedList<>());\n");
        output.append("• 使用并发集合替代：\n");
        output.append("  - 作为列表：CopyOnWriteArrayList\n");
        output.append("  - 作为队列：ConcurrentLinkedQueue\n");
        output.append("  - 作为双端队列：ConcurrentLinkedDeque\n");
        output.append("• 使用显式锁或同步块：\n");
        output.append("  synchronized(list) { list.add(e); }\n");
        
        updateOutput(output.toString());
    }
    
    /**
     * 更新输出文本
     */
    private void updateOutput(String text) {
        tvOutput.append(text);
    }
} 